def climbStairs(n: int) -> int: 
    d1, d2 = 1, 1
    for _ in range(2, n + 1):
        d1, d2 = d1 + d2, d1
    return d1

# 爬楼梯，给定整数n表示总共n级楼梯
# 每次爬1或2级，求不同方案的总数
def climbStairs1(n: int) -> int: 
    # 创建备忘录数组
    # dp[x]表示爬x级台阶的总数
    # 即数组中每个数值即为一个子问题的解
    dp = [0] * (n + 1)
    # 初始化
    dp[0] = dp[1] = 1
    # 逐步求解所有的子问题
    for i in range(2, n + 1):
        # 递推公式：跳到当前台阶i的方案数等于
        # 跳到i-1与i-2级台阶的方案数之和
        dp[i] = dp[i - 1] + dp[i - 2]
    # 备忘录最后一个值即为原问题的解
    return dp[n]

# main
n = 30
ans = climbStairs(n)
print('跳上30级台阶的方案总数为:', ans)
